package com.demo.data.struct.stack;

import java.util.Stack;

/**
问题描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

解题思路
这道题让我们验证输入的字符串是否为括号字符串，包括大括号，中括号和小括号。

这里我们使用栈。

遍历输入字符串

如果当前字符为左半边括号时，则将其压入栈中

如果遇到右半边括号时，分类讨论：

1）如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环

2）若此时栈为空，则直接返回 false

3）若不为对应的左半边括号，反之返回 false
 *
 */
public class 有效的括号 {

	public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
        	if(stack.isEmpty()){
        		stack.push(aChar);
        	}else if(isSym(stack.peek(), aChar)){
        		stack.pop();
        	}else{
        		stack.push(aChar);
        	}
        }
        return stack.isEmpty();
	}

	private static boolean isSym(char c1, char c2) {
        return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
    }

	public static void main(String[] args) {
		System.out.println(有效的括号.isValid("{{[([])()]}}"));
		System.out.println(有效的括号.isValid("{{[([)()]}}"));
	}

}
